// link2.c
// 基于尾插法实现单向链表
#include <stdio.h>
#include <stdlib.h>

// 节点
typedef struct node{
    char data;          //数据域
    struct node *next;  //后继节点
}Node;

typedef struct list
{
    Node* header;   //头指针
    struct node* tail;     //尾指针
    int size;       //大小
}List;

void init(List * list);
void add(List * list , char ch);
void show(List * list);
void insert(List *list , int index , char ch);
char del(List *list , int index);
Node *get(List *list,int index);

int main()
{
    List *list;
    list = malloc(sizeof(List));
    init(list);
    show(list);
    add(list,'A');
    add(list,'B');
    add(list,'C');
    add(list,'D');
    show(list);
    insert(list, 2, 'E');
    show(list);
    char b = del(list, 1);
    printf("%c\n",b);
    show(list);

    return 0;
}

void init(List *list)
{
    list->size = 0;
    list->header = malloc(sizeof(Node));
    // 头指针指向NULL
    list->header->next = NULL;
    list->tail = malloc(sizeof(Node));
    // 尾指针指向头指针
    list->tail = list->header;

}
void add(List * list , char ch)
{
    Node *node = malloc(sizeof(Node));
    node->data = ch;
    node->next = NULL;
    //新节点成为最后一个节点的后继（尾指针的后继就是最后一个节点）
    //空表尾指针指向头指针，非空表尾指针指向最后一个节点
    list->tail->next = node;
    //尾指针指向最后一个（新节点）
    list->tail = node;
    //节点大小自增
    list->size++;

}
void show(List *list)
{
    printf("链表大小：%d\n",list->size);
    printf("遍历:");
    // Node *node = list->header->next;
    // for(int i = 0;i < list->size;i++)
    // {
    //     printf("%c,",node->data);
    //     // 指向后继节点
    //     node = node->next;
    // }
    Node *node = list->header->next;
    while(node != NULL)
    {
        printf("%c,",node->data);
        // 指向后继节点
        node = node->next;
    }
    printf("\n");
}
void insert(List *list , int index , char ch)
{
    // Node * cur = list->header->next;
    // //找到前一个
    // for(int i =0;i< index -1;i++)
    // {
    //     cur = cur->next;
    // }
    // Node *new = malloc(sizeof(Node));
    // new->data = ch;
    // new->next = cur->next;
    // cur->next = new;
    // list->size++;
    Node * node = malloc(sizeof(Node));
    node->data = ch;

    //获得插入的前一个
    Node *p = get(list , index-1);
    // Node *p = list->header;
    // for(int i = 0;i <= index -1 ; i++)
    // {
    //     p = p->next;
    // }
    //插入
    node->next = p->next;
    p->next= node;

    list->size ++;

}
char del(List *list , int index)
{
    // Node * cur = list->header->next;
    // //找到前一个
    // for(int i =0;i< index -1 ;i++)
    // {
    //     cur = cur->next;
    // }
    // Node *n = cur->next;
    // char a = cur->next->data;
    // cur->next = cur->next->next;
    //获得前一个节点
    Node * p = get(list,index-1);
    //要删除的index位置的节点，保存下来一会回收
    Node *n = p->next;
    char a = n->data;
    p->next = p->next->next;
    free(n);
    list->size--;
    return a;
}
Node *get(List *list , int index)
{
    Node *node = list->header;
    for(int i = 0;i<= index;i++)
    {
        node = node->next;
    }
    return node;
}